package com.leet.code.lcof;

public class Code19 {
    public static void main(String[] args) {
        System.out.println(new Code19().isMatch("aaa", "ab*ac*a"));
    }

    public boolean isMatch(String s, String p) {
        int m = s.length() + 1, n = p.length() + 1;
        boolean[][] dp = new boolean[m][n];
        dp[0][0] = true;//代表空字符串可以匹配

        //初始化首行
        for (int j = 2; j < n; j = j + 2) {
            //s第一个定义为空字符串，所以只能跟*匹配 *所在的位置一定是偶数位所以只看偶数位就行
            dp[0][j] = dp[0][j - 2] && p.charAt(j - 1) == '*';
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                //如果匹配规则前一位是*
                if (p.charAt(j - 1) == '*') {
                    //如果i能与p的j-2位匹配，代表a*中a出现了0次，可以匹配
                    if (dp[i][j - 2]) {
                        dp[i][j] = true;
                    }
                    //如果上一位s与j是匹配的，并且该位的s与p中a*中的a相等 代表a*匹配多次还未结束
                    else if (dp[i - 1][j] && s.charAt(i - 1) == p.charAt(j - 2)) {
                        dp[i][j] = true;
                    }
                    //如果上一位s与j是匹配的，并且p的该位是.* 代表.*任何字符串出现n次
                    else if (dp[i - 1][j] && p.charAt(j - 2) == '.') {
                        dp[i][j] = true;
                    }
                    //其他情况都属于不匹配
                    else {
                        dp[i][j] = false;
                    }
                }
                //p的该位不是* 就只能是.或者普通字符串
                else {
                    //如果s的上一位与p的上一位是匹配的 并且 该位的s与p是相同的 那肯定是匹配的
                    if (dp[i - 1][j - 1] && s.charAt(i - 1) == p.charAt(j - 1)) {
                        dp[i][j] = true;
                    }
                    //如果s的上一位与p的上一位是匹配的 并去p的该位置是.代表 .与任何字符匹配
                    else if (dp[i - 1][j - 1] && p.charAt(j - 1) == '.') {
                        dp[i][j] = true;
                    }
                    //其他情况都不能匹配
                    else {
                        dp[i][j] = false;
                    }
                }
            }
        }
        //返回最终匹配的结果
        return dp[m - 1][n - 1];
    }


}
